package algorithm.middle;

import pojo.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindDuplicateSubtrees652 {
    /**
     * 给定一棵二叉树 root，返回所有重复的子树。
     * <p>
     * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
     * <p>
     * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/find-duplicate-subtrees
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param root
     * @return
     */
    Map<String, Integer> map;
    List<TreeNode> list;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        map = new HashMap<>();
        list = new ArrayList<>();
        dfs(root);
        return list;
    }

    /**
     * dfs+hashMap
     *
     * @param node
     * @return 根-左-右
     */
    public String dfs(TreeNode node) {
        if (node == null) {
            //null节点的占位符
            return "n";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(node.val).append("-");
        sb.append(dfs(node.left));
        sb.append(dfs(node.right));
        String key = sb.toString();
        Integer orDefault = map.getOrDefault(key, 0);
        if (orDefault == 1) {
            list.add(node);
        }
        map.put(key, orDefault + 1);
        return sb.toString();
    }
}
